
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main {

    //贪心算法时间复杂度O(N)解决字符串最近问题
    public static void main4(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            int length = in.nextInt();
            String a = in.next();
            String b = in.next();
            String[] strings = new String[length];
            int j = 0;
            while (in.hasNext()) {
                strings[j] = in.next();
                j++;
            }
            in.nextLine(); // 消耗掉 nextInt() 后的换行符
            int prev1 = -1;
            int prev2 = -1;
            int ret = Integer.MAX_VALUE;
            for (int i = 0; i < length; i++) {
                if (strings[i].equals(a)) {
                    prev1 = i;
                    if (prev2 != -1) {
                        ret = Math.min(ret, i - prev2);
                    }
                }
                if (strings[i].equals(b)) {
                    prev2 = i;
                    if (prev1 != -1) {
                        ret = Math.min(ret, i - prev1);
                    }
                }
            }

            System.out.println(ret == Integer.MAX_VALUE ? -1 : ret);
        }
    }


    //最小花费爬楼梯 动态规划
    //太有意思了算法 一行代码困扰我一整晚
    public int minCostClimbingStairs(int[] cost) {
        //dp代表到达该楼梯所需要的最小花费
        int[] dp = new int[cost.length + 1];
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.length];

    }

    public static void main3(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            double good = in.nextDouble();
            char c = in.next().charAt(0);
            int money = 20;
            if (good <= 0) {
                System.out.println(0);
                continue;
            }
            if (good <= 1) {
                System.out.println(money);
                continue;
            } else {
                double more = (good - 1.0);
                int count = 1;
                while (more > 1) {
                    more--;
                    count++;
                }
                if (c == 'y') {
                    money = money + count * 6;
                } else {
                    money = money + count;
                }
                System.out.println(money);

            }
        }
    }

    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String s = in.next();
            Stack<Character> stack = new Stack<>();
            for (char c : s.toCharArray()) {//这种方式可以简明快捷的遍历字符串中的各个字符
                if (!stack.isEmpty() && c == stack.peek()) {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
            StringBuilder s2 = new StringBuilder();
            for (char i : stack) {//这中for-each循环内部用了迭代器 可以从栈底开始遍历 保持入栈顺序
                s2.append(i);
            }
            if (s2.isEmpty()) {
                System.out.println(0);
            } else {
                System.out.println(s2);
            }
        }
    }

    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int L = in.nextInt();
            int R = in.nextInt();
            int count = 0;
            for (int i = L; i <= R; i++) {
                int number = i;
                while (number != 0) {
                    if (number % 10 == 2) {
                        count++;
                        number /= 10;
                    } else {
                        number /= 10;
                    }
                }
            }
            System.out.print(count);
        }

    }

    public ArrayList<Integer> intersection(ArrayList<Integer> nums1, ArrayList<Integer> nums2) {
        // write code here
        ArrayList<Integer> arrayList = new ArrayList<>();
        ArrayList<Integer> copyNum2 = new ArrayList(nums2);
        for (int i = 0; i < nums1.size(); i++) {

        }
        return arrayList;
    }
}
